package listbyorder.access101_200.test112;

import listbyorder.utils.TreeNode;

import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/7 11:24
 */
public class Solution2 {

    // 方法： DFS求解，使用辅助栈
    public boolean hasPathSum(TreeNode root, int sum) {
        Stack<TreeNode> nodeS = new Stack<>();
        Stack<Integer> numS = new Stack<>();
        TreeNode cur = root;
        int curSum = 0;
        while (!nodeS.isEmpty() || cur != null) {
            while (cur != null) {
                nodeS.push(cur);
                curSum += cur.val;
                numS.push(curSum);
                cur = cur.left;
            }
            // 节点为空,则弹出栈顶元素
            cur = nodeS.pop();
            curSum = numS.pop();
            // 判断当前的元素是否满足条件
            if (curSum == sum && cur.left == null && cur.right == null) {
                return true;
            }
            cur = cur.right;
        }
        return false;
    }
}
